package com.apkcore.bl;

/**
 * https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
 */
public class _二进制中1的个数 {
    public static void main(String[] args) {
        System.out.println(new _二进制中1的个数().hammingWeight3(9));
    }

    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }

    public int hammingWeight1(int n) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            ans += (n >> i) & 1;
        }
        return ans;
    }

    public int hammingWeight2(int n) {
        int ans = 0;
        while (n != 0) {
            ans += (n & 1);
            n >>>= 1;
        }
        return ans;
    }

    public int hammingWeight3(int n) {
        int ans = 0;
        // i-=lowbit
        // 10的二进制1010，lowbit为2,表示最后一个1的位置
        // 那么1010去掉后面的10也就是2，那么相当于去掉了最后一个1，可以求下面一个1了。
        int i = n;
        while (i != 0) {
            i -= lowbit(i);
            ans++;
        }
//        for (int i = n; i != 0; i -= lowbit(i)) {
//            ans++;
//        }
        return ans;
    }

    /**
     * 最后一个1所在的位置
     */
    private int lowbit(int x) {
        return x & -x;
    }

}
